<!DOCTYPE html>
<html lang="zh-CN">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>关键算法题解转载 | 月藤的博客</title>
    <meta name="generator" content="VuePress 1.8.0">
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.7.1/katex.min.css">
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/github-markdown-css/2.10.0/github-markdown.min.css">
    <meta name="description" content="简单的介绍">
    
    <link rel="preload" href="/assets/css/0.styles.a2e941e0.css" as="style"><link rel="preload" href="/assets/js/app.54ea76a2.js" as="script"><link rel="preload" href="/assets/js/2.c554ece5.js" as="script"><link rel="preload" href="/assets/js/43.7a4b0851.js" as="script"><link rel="prefetch" href="/assets/js/10.95d63e51.js"><link rel="prefetch" href="/assets/js/11.26e082be.js"><link rel="prefetch" href="/assets/js/12.1f62021c.js"><link rel="prefetch" href="/assets/js/13.9096527c.js"><link rel="prefetch" href="/assets/js/14.86142c70.js"><link rel="prefetch" href="/assets/js/15.1adeebc5.js"><link rel="prefetch" href="/assets/js/16.efcc79e4.js"><link rel="prefetch" href="/assets/js/17.74da5698.js"><link rel="prefetch" href="/assets/js/18.fd808b3a.js"><link rel="prefetch" href="/assets/js/19.8dafe26f.js"><link rel="prefetch" href="/assets/js/20.aed54ab4.js"><link rel="prefetch" href="/assets/js/21.341a5670.js"><link rel="prefetch" href="/assets/js/22.ab8b375c.js"><link rel="prefetch" href="/assets/js/23.28489470.js"><link rel="prefetch" href="/assets/js/24.87aae001.js"><link rel="prefetch" href="/assets/js/25.211ca3bf.js"><link rel="prefetch" href="/assets/js/26.afa4c8f0.js"><link rel="prefetch" href="/assets/js/27.9b98f6f3.js"><link rel="prefetch" href="/assets/js/28.93298733.js"><link rel="prefetch" href="/assets/js/29.e8c038c4.js"><link rel="prefetch" href="/assets/js/3.9d562ae1.js"><link rel="prefetch" href="/assets/js/30.27939f01.js"><link rel="prefetch" href="/assets/js/31.6a9774e8.js"><link rel="prefetch" href="/assets/js/32.f698e967.js"><link rel="prefetch" href="/assets/js/33.5ba4bfb8.js"><link rel="prefetch" href="/assets/js/34.dca90861.js"><link rel="prefetch" href="/assets/js/35.768c1bb2.js"><link rel="prefetch" href="/assets/js/36.6b0a867f.js"><link rel="prefetch" href="/assets/js/37.61156e90.js"><link rel="prefetch" href="/assets/js/38.e390246c.js"><link rel="prefetch" href="/assets/js/39.0fbd0dd1.js"><link rel="prefetch" href="/assets/js/4.e18bc6a8.js"><link rel="prefetch" href="/assets/js/40.4252699c.js"><link rel="prefetch" href="/assets/js/41.2e5b5840.js"><link rel="prefetch" href="/assets/js/42.8fe886c7.js"><link rel="prefetch" href="/assets/js/44.93c2313d.js"><link rel="prefetch" href="/assets/js/45.33dcea60.js"><link rel="prefetch" href="/assets/js/46.681fdf10.js"><link rel="prefetch" href="/assets/js/47.a842a141.js"><link rel="prefetch" href="/assets/js/48.9a03ba74.js"><link rel="prefetch" href="/assets/js/49.a50266b1.js"><link rel="prefetch" href="/assets/js/5.dc6a2d8c.js"><link rel="prefetch" href="/assets/js/50.f2a42406.js"><link rel="prefetch" href="/assets/js/51.444cc3d8.js"><link rel="prefetch" href="/assets/js/52.cf2befd8.js"><link rel="prefetch" href="/assets/js/53.fbe609f8.js"><link rel="prefetch" href="/assets/js/54.a43fb514.js"><link rel="prefetch" href="/assets/js/55.d0c11641.js"><link rel="prefetch" href="/assets/js/56.c6f114d9.js"><link rel="prefetch" href="/assets/js/57.cc386420.js"><link rel="prefetch" href="/assets/js/58.e747d0f6.js"><link rel="prefetch" href="/assets/js/6.c1fd48f0.js"><link rel="prefetch" href="/assets/js/7.32b39b92.js"><link rel="prefetch" href="/assets/js/8.e2284671.js"><link rel="prefetch" href="/assets/js/9.8def3992.js">
    <link rel="stylesheet" href="/assets/css/0.styles.a2e941e0.css">
  </head>
  <body>
    <div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><!----> <span class="site-name">月藤的博客</span></a> <div class="links"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><a href="https://ziphold.gitee.io/blog/#/" target="_blank" rel="noopener noreferrer" class="nav-link external">
  旧博客（停止更新）
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div><div class="nav-item"><a href="https://rattonlzh.github.io/homepage/homepage.html" target="_blank" rel="noopener noreferrer" class="nav-link external">
  常用网址导航（停止更新）
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="Select language" class="dropdown-title"><span class="title">Languages</span> <span class="arrow down"></span></button> <button type="button" aria-label="Select language" class="mobile-dropdown-title"><span class="title">Languages</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/考研专区/关键算法题解转载.html" class="nav-link">
  zh-CN
</a></li><li class="dropdown-item"><!----> <a href="/en/" class="nav-link">
  en-US
</a></li></ul></div></div> <!----></nav></div></header> <div class="sidebar-mask"></div> <aside class="sidebar"><div class="avatar"><img src="/assets/img/avatar.2b77755b.png" alt srcset></div> <div style="z-index: 999"><iframe frameborder="no" border="0" marginwidth="0" marginheight="0" width="298" height="52" src="//music.163.com/outchain/player?type=2&id=28283137&auto=1&height=32"></iframe></div> <nav class="nav-links"><div class="nav-item"><a href="https://ziphold.gitee.io/blog/#/" target="_blank" rel="noopener noreferrer" class="nav-link external">
  旧博客（停止更新）
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div><div class="nav-item"><a href="https://rattonlzh.github.io/homepage/homepage.html" target="_blank" rel="noopener noreferrer" class="nav-link external">
  常用网址导航（停止更新）
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="Select language" class="dropdown-title"><span class="title">Languages</span> <span class="arrow down"></span></button> <button type="button" aria-label="Select language" class="mobile-dropdown-title"><span class="title">Languages</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/考研专区/关键算法题解转载.html" class="nav-link">
  zh-CN
</a></li><li class="dropdown-item"><!----> <a href="/en/" class="nav-link">
  en-US
</a></li></ul></div></div> <!----></nav>  <ul class="sidebar-links"><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>随便说说</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>知识点总结</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading open"><span>考研专区</span> <span class="arrow down"></span></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/考研专区/2021考研政治总结.html" class="sidebar-link">2021考研政治总结</a></li><li><a href="/考研专区/408总结.html" class="sidebar-link">408</a></li><li><a href="/考研专区/关键算法题解转载.html" class="active sidebar-link">关键算法题解转载</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/考研专区/关键算法题解转载.html#morris-中序遍历" class="sidebar-link">Morris 中序遍历</a></li><li class="sidebar-sub-header"><a href="/考研专区/关键算法题解转载.html#字符串匹配算法-rabin-karp" class="sidebar-link">字符串匹配算法——Rabin-Karp</a></li></ul></li><li><a href="/考研专区/数学二总结.html" class="sidebar-link">数学二</a></li><li><a href="/考研专区/英语词组搭配.html" class="sidebar-link">英语</a></li></ul></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>读书笔记</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>开发资料</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>配置记录</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>思维导图</span> <span class="arrow right"></span></p> <!----></section></li><li><a href="/friend_link.html" class="sidebar-link">友情链接</a></li></ul> </aside> <main class="page"> <div class="theme-default-content content__default"><h1 id="关键算法题解转载"><a href="#关键算法题解转载" class="header-anchor">#</a> 关键算法题解转载</h1> <h2 id="morris-中序遍历"><a href="#morris-中序遍历" class="header-anchor">#</a> Morris 中序遍历</h2> <p>我们在中序遍历的时候，一定先遍历左子树，然后遍历当前节点，最后遍历右子树。在常规方法中，我们用递归回溯或者是栈来保证遍历完左子树可以再回到当前节点，但这需要我们付出额外的空间代价。我们需要用一种巧妙地方法可以在 O(1) 的空间下，遍历完左子树可以再回到当前节点。我们希望当前的节点在遍历完当前点的前驱之后被遍历，我们可以考虑修改它的前驱节点的 right 指针。当前节点的前驱节点的 right 指针可能本来就指向当前节点（前驱是当前节点的父节点），也可能是当前节点左子树最右下的节点。如果是后者，我们希望遍历完这个前驱节点之后再回到当前节点，可以将它的 right 指针指向当前节点。</p> <p>Morris 中序遍历的一个重要步骤就是寻找当前节点的前驱节点，并且 Morris 中序遍历寻找下一个点始终是通过转移到 right 指针指向的位置来完成的。</p> <p>如果当前节点没有左子树，则遍历这个点，然后跳转到当前节点的右子树。
如果当前节点有左子树，那么它的前驱节点一定在左子树上，我们可以在左子树上一直向右行走，找到当前点的前驱节点。
如果前驱节点没有右子树，就将前驱节点的 right 指针指向当前节点。这一步是为了在遍历完前驱节点后能找到前驱节点的后继，也就是当前节点。
如果前驱节点的右子树为当前节点，说明前驱节点已经被遍历过并被修改了right 指针，这个时候我们重新将前驱的右孩子设置为空，遍历当前的点，然后跳转到当前节点的右子树。</p> <p>因此我们可以得到这样的代码框架：</p> <div class="language-c++ extra-class"><pre class="language-text"><code>TreeNode *cur = root, *pre = nullptr;
while (cur) {
    if (!cur-&gt;left) {
        // ...遍历 cur
        cur = cur-&gt;right;
        continue;
    }
    pre = cur-&gt;left;
    while (pre-&gt;right &amp;&amp; pre-&gt;right != cur) {
        pre = pre-&gt;right;
    }
    if (!pre-&gt;right) {
        pre-&gt;right = cur;
        cur = cur-&gt;left;
    } else {
        pre-&gt;right = nullptr;
        // ...遍历 cur
        cur = cur-&gt;right;
    }
}
</code></pre></div><p>作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/solution/er-cha-sou-suo-shu-zhong-de-zhong-shu-by-leetcode-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。</p> <hr> <h2 id="字符串匹配算法-rabin-karp"><a href="#字符串匹配算法-rabin-karp" class="header-anchor">#</a> 字符串匹配算法——Rabin-Karp</h2> <p>​    Rabin Karp算法的思想基于暴力匹配法，字符串比较的时间复杂度是O(m)，整数比较的时间复杂度却是O(1)。所以，Rabin Karp算法在暴力匹配法的基础上引入哈希表，把要比较的字符串转换为整数，即哈希表的索引是字符串，值是整数。根据哈希表的性质可以推断出：在哈希表中，1）两个不同的字符串可以对应相等的值；2）两个相同的字符串必须对应相等的值；3）两个不等的值肯定对应两个不同的字符串。所以，当两个字符串的值相同时，Rabin Karp算法仍然需要逐一比较两个字符串中的字符。但是，和暴力匹配法相比，Rabin Karp算法避免了比较两个哈希值不等的字符串，从而降低了字符串比较的时间复杂度。</p> <p>版权声明：本文为博主原创文章，遵循<a href="http://creativecommons.org/licenses/by-sa/4.0/" target="_blank" rel="noopener noreferrer"> CC 4.0 BY-SA <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a>版权协议，转载请附上原文出处链接和本声明。</p> <p>本文链接：https://blog.csdn.net/yuanshine/article/details/81608487</p> <hr> <h3 id="哈希法判断一个树是否是另一个树的子树"><a href="#哈希法判断一个树是否是另一个树的子树" class="header-anchor">#</a> 哈希法判断一个树是否是另一个树的子树</h3> <p>方法三：树哈希
思路：考虑把每个子树都映射成一个唯一的数，如果 t 对应的数字和 s 中任意一个子树映射的数字相等，则 t 是 s 的某一棵子树</p> <p>我们可以用「埃氏筛法」或者「欧拉筛法」求出前 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>arg</mi><mi>π</mi><mo>(</mo><mi>max</mi><mo>{</mo><mi mathvariant="normal">∣</mi><mi>s</mi><mi mathvariant="normal">∣</mi><mo separator="true">,</mo><mi mathvariant="normal">∣</mi><mi>t</mi><mi mathvariant="normal">∣</mi><mo>}</mo></mrow><annotation encoding="application/x-tex">\arg \pi (\max \{ |s|, |t| \}</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mop">ar<span style="margin-right:0.01389em;">g</span></span><span class="mord mathit" style="margin-right:0.03588em;">π</span><span class="mopen">(</span><span class="mop">max</span><span class="mopen">{</span><span class="mord mathrm">∣</span><span class="mord mathit">s</span><span class="mord mathrm">∣</span><span class="mpunct">,</span><span class="mord mathrm">∣</span><span class="mord mathit">t</span><span class="mord mathrm">∣</span><span class="mclose">}</span></span></span></span> 个素数（其中 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>π</mi><mo>(</mo><mi>x</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">\pi (x)</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.03588em;">π</span><span class="mopen">(</span><span class="mord mathit">x</span><span class="mclose">)</span></span></span></span> 表示 x以内素数个数，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>arg</mi><mi>π</mi><mo>(</mo><mi>x</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">\arg \pi (x)</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mop">ar<span style="margin-right:0.01389em;">g</span></span><span class="mord mathit" style="margin-right:0.03588em;">π</span><span class="mopen">(</span><span class="mord mathit">x</span><span class="mclose">)</span></span></span></span> 为它的反函数，表示有多少以内包含 x 个素数，这个映射是不唯一的，我们取最小值），然后 DFS 计算哈希值，最后比较 s 的所有子树是否有和 t 相同的哈希值即可。</p> <p>作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/subtree-of-another-tree/solution/ling-yi-ge-shu-de-zi-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。</p></div> <footer class="page-edit"><!----> <!----> <a rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.zh"><img alt="知识共享许可协议" src="" style="border-width:0"></a><br>本作品采用<a rel="license" href="http://creativecommons.org/licenses/by/4.0/">知识共享署名 4.0 国际许可协议</a>进行许可。

   
</footer> <div class="page-nav"><p class="inner"><span class="prev">
      ←
      <a href="/考研专区/408总结.html" class="prev">
        408
      </a></span> <span class="next"><a href="/考研专区/数学二总结.html">
        数学二
      </a>
      →
    </span></p></div>  <footer style="text-align:center;"><a href="https://beian.miit.gov.cn">
    粤ICP备2021020303号</a></footer></main></div><div class="global-ui"><!----></div></div>
    <script src="/assets/js/app.54ea76a2.js" defer></script><script src="/assets/js/2.c554ece5.js" defer></script><script src="/assets/js/43.7a4b0851.js" defer></script>
  </body>
</html>
